package dp;

/**
 * @author : Rookie
 * @description : 整数拆分
 * @date : 2024/1/14
 */
public class IntegerSpilt {

    public static void main(String[] args) {
        // 将10进行拆分 得到乘积的最大值
        int target = 10;
        int result = spilt(target);
        System.out.println(result);
    }

    private static int spilt(int target) {
        // dp[i]表示将i拆分之后 所得乘积最大值
        int[] dp = new int[target+1];
        dp[2] = 1;
        for (int i = 3; i <= target; i++) {
            for (int j = 1;j<i;j++) {
                // 有两种情况，一种是拆分成2个数，一种是拆分成多个 对dp[i-j]继续进行拆分
                // 这里每次每次都要加入dp[i]进行比较 原因是j不同时，算出来的dp[i]也不同，要确定dp[i]是整数i拆分后乘积的最大值
                dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
                System.out.println("j="+j + ", dp["+i+"]="+dp[i]);
            }
        }
        Common.print1dArr(dp);
        return dp[target];
    }
}
